package string

func GetNext(s string) []int {
	var k, i, n = -1, 1, len(s)
	next := make([]int, n)
	next[0] = -1
	sb := []byte(s)
	for i < n-1 {
		if k < 0 || sb[i] == sb[k] {
			next[i+1] = k + 1
			i++
			k++
		} else {
			k = next[k]
		}
	}
	return next
}

func Match(s string, p string) int {
	var i, j, n, m = 0, 0, len(s), len(p)
	sb, pb := []byte(s), []byte(p)
	next := GetNext(p)
	for i < n && j < m {
		if j < 0 || sb[i] == pb[j] {
			i++
			j++
		} else {
			j = next[j]
		}
	}

	if j >= m {
		return i - j
	}
	return -1
}
